package com.fwpsl.graph.minimumspanningtree;

import com.fwpsl.graph.Edge;
import com.fwpsl.graph.Graph;
import com.fwpsl.graph.Vertex;

import java.util.*;

/**
 * @author: 风戏fw
 * @date: 2024/4/6
 * @description: Kruskal算法是一种用来查找加权连通图的最小生成树的算法。它的基本思想是按照权值从小到大的顺序选择边，
 * 并保证所选的边不构成回路。具体实现过程中，首先将图中的所有边按照权值从小到大进行排序，然后从权值最小的边开始，
 * 依次判断这条边的两个端点是否在同一个连通块中。如果不在同一个连通块中，则将这条边加入到最小生成树的边集合中，
 * 并将这两个端点合并到同一个连通块中。重复这个过程，直到最小生成树的边集合中包含了所有节点。
 * <p>
 * Kruskal算法是一种贪心算法，因为它每一步都选择当前情况下最优的解（即权值最小的边），
 * 并且希望这样的局部最优解能够导致全局最优解（即最小生成树）。
 * <p>
 * 在实际应用中，Kruskal算法常用于解决各种网络优化问题，如电路布线、通信网络设计、物流运输路径规划等。
 * 在这些场景中，通常需要将多个节点（如城市、基站、仓库等）以最小的成本连接起来，形成一个连通且成本最低的网络结构，
 * 而Kruskal算法正是解决这类问题的有效工具。
 */
public class Kruskal {

    /**
     * 并查集（Union Find）数据结构来检查添加一条边是否会形成回路。并查集通过维护每个节点的父节点来实现对连通性的快速查询和合并。
     */
    static class UnionFind<T> {
        private Map<Vertex<T>, Vertex<T>> parentVertexMap;

        UnionFind(List<Vertex<T>> vertices) {
            parentVertexMap = new HashMap<>();
            for (Vertex<T> v : vertices) {
                parentVertexMap.put(v, v);
            }
        }

        /**
         * 查找节点的根节点
         *
         * @param vertex
         * @return
         */
        Vertex<T> find(Vertex<T> vertex) {
            if (parentVertexMap.get(vertex) != vertex) {
                return find(parentVertexMap.get(vertex));
            }
            return parentVertexMap.get(vertex);
        }

        /**
         * 合并两个连通块
         *
         * @param x
         * @param y
         */
        void union(Vertex<T> x, Vertex<T> y) {
            Vertex<T> rootX = find(x);
            Vertex<T> rootY = find(y);
            if (rootX != rootY) {
                parentVertexMap.put(rootX, rootY);
            }
        }
    }

    public static <T> void kruskal(Graph<T> graph) {
        // 图中的边集，并按权重排序
        List<Edge<T>> edges = graph.getEdges();
        Collections.sort(edges, Comparator.comparingDouble(Edge::getWeight));

        // 并查集
        UnionFind uf = new UnionFind(graph.getVertices());

        // 连通边集
        List<Edge> mst = new ArrayList<>();
        for (Edge e : edges) {
            Vertex<T> x = uf.find(e.getSource());
            Vertex<T> y = uf.find(e.getDestination());
            if (x != y) {
                mst.add(e);
                uf.union(x, y);
            }
        }

        if (mst.size() != graph.getVertexNum() - 1) {
            System.out.println("图形未连通");
            return;
        }

        System.out.println("构建的MST中的边：");
        for (Edge e : mst) {
            System.out.println(e.getSource().getData() + " -- " + e.getDestination().getData() + " == " + e.getWeight());
        }
    }

    public static void main(String[] args) {
        int[][] graphEdgeArr = {
                {0, 4, 0, 0, 0, 0, 0, 8, 0},
                {4, 0, 8, 0, 0, 0, 0, 11, 0},
                {0, 8, 0, 7, 0, 4, 0, 0, 2},
                {0, 0, 7, 0, 9, 14, 0, 0, 0},
                {0, 0, 0, 9, 0, 10, 0, 0, 0},
                {0, 0, 4, 14, 10, 0, 2, 0, 0},
                {0, 0, 0, 0, 0, 2, 0, 1, 6},
                {8, 11, 0, 0, 0, 0, 1, 0, 7},
                {0, 0, 2, 0, 0, 0, 6, 7, 0}
        };
        Graph<Integer> graph = Graph.buildIntGraph(graphEdgeArr);

        kruskal(graph);
    }
}
